package com.shm.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 219. 存在重复元素 II
 * 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [1,2,3,1], k = 3
 * 输出: true
 * 示例 2:
 *
 * 输入: nums = [1,0,1,1], k = 1
 * 输出: true
 * 示例 3:
 *
 * 输入: nums = [1,2,3,1,2,3], k = 2
 * 输出: false
 *
 * @author SHM
 */
public class ContainsNearbyDuplicate {
    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                List<Integer> list = map.get(nums[i]);
                if (i-list.get(0)<=k){
                    return true;
                }
                list.set(0,i);
            }else{
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(nums[i],list);
            }
        }
        return false;
    }

    /**
     * 方法一 （线性搜索） 【超时】
     * 思路
     * 将每个元素与它之前的 kk 个元素中比较查看它们是否相等。
     *
     * 算法
     *
     * 这个算法维护了一个 kk 大小的滑动窗口，然后在这个窗口里面搜索是否存在跟当前元素相等的元素。
     *
     * 时间复杂度分析
     *
     * 时间复杂度：O(n \min(k,n))O(nmin(k,n))
     * 每次搜索都要花费 O(\min(k, n))O(min(k,n)) 的时间，哪怕kk比nn大，一次搜索中也只需比较 nn 次。
     *
     * 空间复杂度：O(1)O(1)
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/contains-duplicate-ii/solution/cun-zai-zhong-fu-yuan-su-ii-by-leetcode/
     * @param nums
     * @param k
     * @return
     */
    public  boolean containsNearbyDuplicate_2(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = Math.max(i-k,0); j < i; j++) {
                if (nums[i]==nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean containsNearbyDuplicate_1(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j <= i+k&&j<nums.length; j++) {
                if (nums[i]==nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean containsNearbyDuplicate_3(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])&&i-map.get(nums[i])<=k){
                return true;
            }
            map.put(nums[i],i);
        }
        return false;
    }
    public static void main(String[] args) {
        int[] nums={1,0,1,1};
        int k = 1;
        containsNearbyDuplicate(nums,k);
    }
}
